package com.gitee.wsl.lang.bits

import com.gitee.wsl.ext.base.Arrays.arraycopy
import kotlin.jvm.JvmOverloads
import kotlin.jvm.Transient
import kotlin.math.max
import kotlin.math.min

/**
 * This class implements a set of bits that grows as needed. Each bit of the
 * bit set represents a `boolean` value. The values of a
 * `SparseBitSet` are indexed by non-negative integers.
 * Individual indexed values may be examined, set, cleared, or modified by
 * logical operations. One `SparseBitSet` or logical value may be
 * used to modify the contents of (another) `SparseBitSet` through
 * logical **AND**, logical **inclusive OR**, logical **exclusive
 * OR**, and **And NOT** operations over all or part of the bit sets.
 *
 *
 * All values in a bit set initially have the value `false`.
 *
 *
 * Every bit set has a current size, which is the number of bits of space
 * *nominally* in use by the bit set from the first set bit to just after
 * the last set bit. The length of the bit set effectively tells the position
 * available after the last bit of the SparseBitSet.
 *
 *
 * The maximum cardinality of a `SparseBitSet` is
 * `Integer.MAX_VALUE`, which means the bits of a
 * `SparseBitSet` are labelled `
 * 0`&nbsp;..&nbsp;`Integer.MAX_VALUE&nbsp;&nbsp;1`.
 * After the last set bit of a `SparseBitSet`, any attempt to find
 * a subsequent bit (*nextSetBit*()), will return an value of 1.
 * If an attempt is made to use *nextClearBit*(), and all the bits are
 * set from the starting position of the search to the bit labelled
 * `Integer.MAX_VALUE&nbsp;&nbsp;1`, then similarly 1
 * will be returned.
 *
 *
 * Unless otherwise noted, passing a null parameter to any of the methods in
 * a `SparseBitSet` will result in a
 * `NullPointerException`.
 *
 *
 * A `SparseBitSet` is not safe for multi-threaded use without
 * external synchronization.
 *
 * @author      Bruce K. Haddon
 * @author      Arthur van Hoff
 * @author      Michael McCloskey
 * @author      Martin Buchholz
 * @version     1.0, 2009-03-17
 * @since       1.6
 */
open class SparseBitSet protected constructor(
    capacity: Int,
    compactionCount: Int
) {

    /**
     * This value controls for format of the toString() output.
     * @see .toStringCompaction
     */
    @Transient
    protected var compactionCount: Int

    /**
     * The storage for this SparseBitSet. The *i*th bit is stored in a word
     * represented by a long value, and is at bit position `i % 64`
     * within that word (where bit position 0 refers to the least significant bit
     * and 63 refers to the most significant bit).
     *
     *
     * The words are organized into blocks, and the blocks are accessed by two
     * additional levels of array indexing.
     */
    @Transient
    protected var bits: Array<Array<LongArray?>?> = arrayOfNulls(capacity)

    /**
     * For the current size of the bits array, this is the maximum possible
     * length of the bit set, i.e., the index of the last possible bit, plus one.
     * Note: this not the value returned by *length*().
     * @see .resize
     * @see .length
     */
    @Transient
    protected var bitsLength: Int = 0

    /**
     * Holds reference to the cache of statistics values computed by the
     * UpdateStrategy
     * @see SparseBitSet.Cache
     *
     * @see SparseBitSet.UpdateStrategy
     */
    @Transient
    protected var cache: Cache? = null

    //=============================================================================
    //  Stack structures used for recycling blocks
    //=============================================================================
    /**
     * A spare level 3 block is kept for use when scanning. When a target block
     * is needed, and there is not already one in the bit set, the spare is
     * provided. If non-zero values are placed into this block, it is moved to the
     * resulting set, and a new spare is acquired. Note: a new spare needs to
     * be allocated when the set is cloned (so that the spare is not shared
     * between two sets).
     */
    @Transient
    protected lateinit var spare: LongArray

    /**
     * Constructs an empty bit set with the default initial size.
     * Initially all bits are effectively `false`.
     *
     * @since       1.6
     */
    constructor() : this(1, compactionCountDefault)

    /**
     * Creates a bit set whose initial size is large enough to efficiently
     * represent bits with indices in the range `0` through
     * at least `nbits-1`. Initially all bits are effectively
     * `false`.
     *
     *
     * No guarantees are given for how large or small the actual object will be.
     * The setting of bits above the given range is permitted (and will perhaps
     * eventually cause resizing).
     *
     * @param       nbits the initial provisional length of the SparseBitSet
     * @throws      NegativeArraySizeException if the specified initial
     * length is negative
     * @see .SparseBitSet
     * @since       1.6
     */
    constructor(nbits: Int) : this(nbits, compactionCountDefault)


    /*  Programming notes:

        i, j, and k are used to hold values that are actual bit indices (i.e.,
        the index (label) of the bit within the user's view of the bit set).

        u, v, and w, are used to hold values that refer to the indices of the
        words in the set array that are used to hold the bits (with 64 bits per
        word). These variable names, followed by 1, 2, or 3, refer to the component
        "level" parts of the complete word index.

        word (where used) is a potential entry to or from a block, containing 64
        bits of the bit set. The prefixes a, b, result, etc., refer to the bit
        sets from which these are coming or going. Without a prefix, or with the
        prefix "a," the set in question is "this" set (see next paragraph).

        Operations are conceived to be in the form a.op(b), thus in the discussion
        (not in the public Javadoc documentation) the two sets are referred to a
        "a" and "b", where the set referred to by "this" is usually set a.
        Hence, reference to set a is usually implicit, but set b will usually be
        explicit. Variables beginning with these letters hold values relevant to
        the corresponding set, and, in particular, these letters followed by
        1, 2, and 3 are used to refer to the corresponding (current) level1,
        level3 area, and level3 block, arrays.

        The resizing of the table takes place as necessary. In this regard, it is
        worth noting that the table is grown, but never shrunk (except in a new
        object formed by cloning).

        Similarly, care it taken to ensure that any supplied reference to a bit
        set (other than this) has an opportunity to fail for being null before
        any other set (including this) has its state changed. For the most
        part, this is allowed to happen "naturally," but the Strategies incorporate
        an explicit check when necessary.

        There is a amount of (almost) repetitive scanning code in many of the
        "singe bit" methods. The intent is that these methods for SparseBitSet be
        as small and as fast as possible.

        For the scanning of complete sets, or for ranges within complete sets,
        all of the scanning logic is built into one (somewhat enormous) method,
        setScanner(). This contains all the considerations for matching up
        corresponding level 3 blocks (if they exist), and then uses a Strategy
        object to do the processing on those level3 blocks. This keeps all
        the scanning and optimization logic in one place, and the Strategies are
        reasonably simple (see the definition of AbstractStrategy for a discussion
        of the tasks that must be defined therein).

        The test for index i (the first index in all cases) being in range is
        rather perverse, but the idea was to keep the actual number of comparisons
        to a minimum, hence the check is for "(i + 1) < 1". This is almost but not
        quite equivalent to "i < 0", although it is for all values of i except
        i=Integer.MAX_VALUE. In this latter case, (i + 1) "overflows" to
        -(Integer.MAX_VALUE + 1), and thus appears to be less than 1, and thus the
        check picks up the other disallowed case. Let us hope the compiler never
        gets smart enough to try to do the apparent optimisation! */
    /**
     * Constructor for a new (sparse) bit set. All bits initially are effectively
     * `false`. This is a internal constructor that collects all the
     * needed actions to initialise the bit set.
     *
     *
     * The capacity is taken to be a *suggestion* for a size of the bit set,
     * in bits. An appropiate table size (a power of two) is then determined and
     * used. The size will be grown as needed to accomodate any bits addressed
     * during the use of the bit set.
     *
     * @param       capacity a size in terms of bits
     * @param       compactionCount the compactionCount to be inherited (for
     * internal generation)
     * @exception   NegativeArraySizeException if the specified initial size
     * is negative
     * @since       1.6
     */
    init {
        /*  Array size is computed based on this being a capacity given in bits. */
        if (capacity < 0)  // capacity can't be negative -- could only come from
            throw IllegalArgumentException( //  an erroneous user given
                "(requested capacity=$capacity) < 0"
            ) // nbits value

        resize(capacity - 1) //  Resize takes last usable index
        this.compactionCount = compactionCount
        /*  Ensure there is a spare level 3 block for the use of the set scanner.*/
        constructorHelper()
        statisticsUpdate()
    }

    /**
     * Performs a logical **AND** of the addressed target bit with the argument
     * value. This bit set is modified so that the addressed bit has the value
     * `true` if and only if it both initially had the value
     * `true` and the argument value is also `true`.
     *
     * @param       i a bit index
     * @param       value a boolean value to **AND** with that bit
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun and(i: Int, value: Boolean) {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        if (!value) clear(i)
    }

    /**
     * Performs a logical **AND** of this target bit set with the argument bit
     * set within the given range of bits. Within the range, this bit set is
     * modified so that each bit in it has the value `true` if and only
     * if it both initially had the value `true` and the corresponding
     * bit in the bit set argument also had the value `true`. Outside
     * the range, this set is not changed.
     *
     * @param       i index of the first bit to be included in the operation
     * @param       j index after the last bit to included in the operation
     * @param       b a SparseBitSet
     * @exception   IndexOutOfBoundsException if `i` is negative or
     * equal to Integer.MAX_VALUE, or `j` is negative,
     * or `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun and(i: Int, j: Int, b: SparseBitSet?) {
        setScanner(i, j, b, andStrategy)
    }

    /**
     * Performs a logical **AND** of this target bit set with the argument bit
     * set. This bit set is modified so that each bit in it has the value
     * `true` if and only if it both initially had the value
     * `true` and the corresponding bit in the bit set argument also
     * had the value `true`.
     *
     * @param       b a SparseBitSet
     * @since       1.6
     */
    fun and(b: SparseBitSet) {
        nullify(min(bits.size.toDouble(), b.bits.size.toDouble()).toInt()) // Optimisation
        setScanner(
            0,
            min(bitsLength.toDouble(), b.bitsLength.toDouble()).toInt(), b, andStrategy
        )
    }

    /**
     * Performs a logical **AndNOT** of the addressed target bit with the
     * argument value. This bit set is modified so that the addressed bit has the
     * value `true` if and only if it both initially had the value
     * `true` and the argument value is `false`.
     *
     * @param       i a bit index
     * @param       value a boolean value to AndNOT with that bit
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun andNot(i: Int, value: Boolean) {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        if (value) clear(i)
    }

    /**
     * Performs a logical **AndNOT** of this target bit set with the argument
     * bit set within the given range of bits. Within the range, this bit set is
     * modified so that each bit in it has the value `true` if and only
     * if it both initially had the value `true` and the corresponding
     * bit in the bit set argument has the value `false`. Outside
     * the range, this set is not changed.
     *
     * @param       i index of the first bit to be included in the operation
     * @param       j index after the last bit to included in the operation
     * @param       b the SparseBitSet with which to mask this SparseBitSet
     * @exception   IndexOutOfBoundsException if `i` is negative or
     * equal to Integer.MAX_VALUE, or `j` is negative,
     * or `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun andNot(i: Int, j: Int, b: SparseBitSet?) {
        setScanner(i, j, b, andNotStrategy)
    }

    /**
     * Performs a logical **AndNOT** of this target bit set with the argument
     * bit set. This bit set is modified so that each bit in it has the value
     * `true` if and only if it both initially had the value
     * `true` and the corresponding bit in the bit set argument has
     * the value `false`.
     *
     * @param       b the SparseBitSet with which to mask this SparseBitSet
     * @since       1.6
     */
    fun andNot(b: SparseBitSet) {
        setScanner(
            0,
            min(bitsLength.toDouble(), b.bitsLength.toDouble()).toInt(), b, andNotStrategy
        )
    }

    /**
     * Returns the number of bits set to `true` in this
     * `SparseBitSet`.
     *
     * @return      the number of bits set to true in this SparseBitSet
     * @since       1.6
     */
    fun cardinality(): Int {
        statisticsUpdate() // Update size, cardinality and length values
        return cache!!.cardinality
    }

    /**
     * Sets the bit at the specified index to `false`.
     *
     * @param       i a bit index.
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE.
     * @since       1.6
     */
    fun clear(i: Int) {
        /*  In the interests of speed, no check is made here on whether the
            level3 block goes to all zero. This may be found and corrected
            in some later operation. */
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        if (i >= bitsLength) return
        val w = i shr SHIFT3
        var a2: Array<LongArray?>?
        if ((bits[w shr SHIFT1].also { a2 = it }) == null) return
        var a3: LongArray?
        if ((a2!![(w shr SHIFT2) and MASK2].also { a3 = it }) == null) return
        a3!![w and MASK3] = a3!![w and MASK3] and (1L shl i).inv() //  Clear the indicated bit
        cache!!.hash = 0 //  Invalidate size, etc.,
    }

    /**
     * Sets the bits from the specified `i` (inclusive) to the
     * specified `j` (exclusive) to `false`.
     *
     * @param       i index of the first bit to be cleared
     * @param       j index after the last bit to be cleared
     * @exception   IndexOutOfBoundsException if `i` is negative or
     * equal to Integer.MAX_VALUE, or `j` is negative,
     * or `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun clear(i: Int, j: Int) {
        setScanner(i, j, null, clearStrategy)
    }

    /**
     * Sets all of the bits in this `SparseBitSet` to
     * `false`.
     *
     * @since       1.6
     */
    fun clear() {
        /*  This simply resets to null all the entries in the set. */
        nullify(0)
    }

    /**
     * Cloning this `SparseBitSet` produces a new
     * `SparseBitSet` that is *equal*() to it. The clone of the
     * bit set is another bit set that has exactly the same bits set to
     * `true` as this bit set.
     *
     *
     * Note: the actual space allocated to the clone tries to minimise the actual
     * amount of storage allocated to hold the bits, while still trying to
     * keep access to the bits being a rapid as possible. Since the space
     * allocated to a `SparseBitSet` is not normally decreased,
     * replacing a bit set by its clone may be a way of both managing memory
     * consumption and improving the rapidity of access.
     *
     * @return      a clone of this SparseBitSet
     * @since       1.6
     */
//    override fun clone(): SparseBitSet {
//        try {
//            val result = super.clone() as SparseBitSet
//            /*  Clear out the shallow copy of the set array (which contains just
//                copies of the references from this set), and then replace these
//                by a deep copy (created by a "copy" from the set being cloned . */
//            result.bits = null
//            result.resize(1)
//            /*  Ensure the clone is not sharing a copy of a spare block with
//                the cloned set, nor the cache set, nor any of the visitors (which
//                are linked to their parent object) (Not all visitors actually use
//                this link to their containing object, but they are reset here just
//                in case of  future changes). */
//            result.constructorHelper()
//            result.equalsStrategy = null
//            result.setScanner(0, bitsLength, this, copyStrategy)
//            return result
//        } catch (ex: CloneNotSupportedException) {
//            /*  This code has not been unit tested. Inspection offers hope
//                that is will work, but it likely never to be used. */
//            throw InternalError(ex.message)
//        }
//    }

    fun clone(): SparseBitSet{
        TODO()
    }

    /**
     * Compares this object against the specified object. The result is
     * `true` if and only if the argument is not `null`
     * and is a `SparseBitSet` object that has exactly the same bits
     * set to `true` as this bit set. That is, for every nonnegative
     * `i` indexing a bit in the set,
     * <pre>((SparseBitSet)obj).get(i) == this.get(i)</pre>
     * must be true.
     *
     * @param       obj the Object with which to compare
     * @return      `true` if the objects are equivalent;
     * `false` otherwise.
     * @since       1.6
     */
    override fun equals(obj: Any?): Boolean {
        /*  Sanity and quick checks. */
        if (obj !is SparseBitSet) return false
        val b = obj
        if (this === b) return true // Identity


        /*  Do the real work.  */
        if (equalsStrategy == null) equalsStrategy = EqualsStrategy()

        setScanner(
            0,
            max(bitsLength.toDouble(), b.bitsLength.toDouble()).toInt(), b, equalsStrategy!!
        )
        return equalsStrategy!!.result
    }

    /**
     * Sets the bit at the specified index to the complement of its current value.
     *
     * @param       i the index of the bit to flip
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun flip(i: Int) {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        val w = i shr SHIFT3
        val w1 = w shr SHIFT1
        val w2 = (w shr SHIFT2) and MASK2

        if (i >= bitsLength) resize(i)
        var a2: Array<LongArray?>?
        if ((bits[w1].also { a2 = it }) == null) {
            bits[w1] = arrayOfNulls(LENGTH2)
            a2 = bits[w1]
        }
        var a3: LongArray?
        if ((a2!![w2].also { a3 = it }) == null) {
            a2!![w2] = LongArray(LENGTH3)
            a3 = a2!![w2]
        }
        a3!![w and MASK3] = a3!![w and MASK3] xor (1L shl i) //Flip the designated bit
        cache!!.hash = 0 //  Invalidate size, etc., values
    }

    /**
     * Sets each bit from the specified `i` (inclusive) to the
     * specified `j` (exclusive) to the complement of its current
     * value.
     *
     * @param       i index of the first bit to flip
     * @param       j index after the last bit to flip
     * @exception   IndexOutOfBoundsException if `i` is negative or is
     * equal to Integer.MAX_VALUE, or `j` is negative, or
     * `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun flip(i: Int, j: Int) {
        setScanner(i, j, null, flipStrategy)
    }

    /**
     * Returns the value of the bit with the specified index. The value is
     * `true` if the bit with the index `i` is currently set
     * in this `SparseBitSet`; otherwise, the result is
     * `false`.
     *
     * @param       i the bit index
     * @return      the boolean value of the bit with the specified index.
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun get(i: Int): Boolean {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        val w = i shr SHIFT3

        var a2: Array<LongArray?>? = null
        var a3: LongArray? = null
        return i < bitsLength
                && (bits[w shr SHIFT1].also { a2 = it }) != null
                && (a2!![(w shr SHIFT2) and MASK2].also { a3 = it }) != null
                && ((a3!![w and MASK3] and (1L shl i)) != 0L)
    }

    /**
     * Returns a new `SparseBitSet` composed of bits from this
     * `SparseBitSet` from `i` (inclusive) to `j`
     * (exclusive).
     *
     * @param       i index of the first bit to include
     * @param       j index after the last bit to include
     * @return      a new SparseBitSet from a range of this SparseBitSet
     * @exception   IndexOutOfBoundsException if `i` is negative or is
     * equal to Integer.MAX_VALUE, or `j` is negative, or
     * `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun get(i: Int, j: Int): SparseBitSet {
        val result = SparseBitSet(j, compactionCount)
        result.setScanner(i, j, this, copyStrategy)
        return result
    }

    /**
     * Returns a hash code value for this bit set. The hash code depends only on
     * which bits have been set within this `SparseBitSet`. The
     * algorithm used to compute it may be described as follows.
     *
     *
     * Suppose the bits in the `SparseBitSet` were to be stored in an
     * array of `long` integers called, say, `bits`, in such
     * a manner that bit `i` is set in the `SparseBitSet`
     * (for nonnegative values of  `i`) if and only if the expression
     * <pre>
     * ((i&gt;&gt;6) &lt; bits.length) &amp;&amp; ((bits[i&gt;&gt;6] &amp; (1L &lt;&lt; (bit &amp; 0x3F))) != 0)
    </pre> *
     * is true. Then the following definition of the `hashCode` method
     * would be a correct implementation of the actual algorithm:
     * <pre>
     * public int hashCode()
     * {
     * long hash = 1234L;
     * for( int i = bits.length; --i &gt;= 0; )
     * hash ^= bits[i] * (i + 1);
     * return (int)((h &gt;&gt; 32) ^ h);
     * }</pre>
     * Note that the hash code values change if the set of bits is altered.
     *
     * @return      a hash code value for this bit set
     * @since       1.6
     * @see Object.equals
     * @see java.util.Hashtable
     */
    override fun hashCode(): Int {
        statisticsUpdate()
        return cache!!.hash
    }

    /**
     * Returns true if the specified `SparseBitSet` has any bits
     * within the given range `i` (inclusive) to `j`
     * (exclusive) set to `true` that are also set to `true`
     * in the same range of this `SparseBitSet`.
     *
     * @param       i index of the first bit to include
     * @param       j index after the last bit to include
     * @param       b the SparseBitSet with which to intersect
     * @return      the boolean indicating whether this SparseBitSet intersects the
     * specified SparseBitSet
     * @exception   IndexOutOfBoundsException if `i` is negative or
     * equal to Integer.MAX_VALUE, or `j` is negative,
     * or `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun intersects(i: Int, j: Int, b: SparseBitSet?): Boolean {
        setScanner(i, j, b, intersectsStrategy)
        return intersectsStrategy.result
    }

    /**
     * Returns true if the specified `SparseBitSet` has any bits set to
     * `true` that are also set to `true` in this
     * `SparseBitSet`.
     *
     * @param       b a SparseBitSet with which to intersect
     * @return      boolean indicating whether this SparseBitSet intersects the
     * specified SparseBitSet
     * @since       1.6
     */
    fun intersects(b: SparseBitSet): Boolean {
        setScanner(
            0,
            max(bitsLength.toDouble(), b.bitsLength.toDouble()).toInt(), b, intersectsStrategy
        )
        return intersectsStrategy.result
    }

    val isEmpty: Boolean
        /**
         * Returns true if this `SparseBitSet` contains no bits that are
         * set to `true`.
         *
         * @return      the boolean indicating whether this SparseBitSet is empty
         * @since       1.6
         */
        get() {
            statisticsUpdate()
            return cache!!.cardinality == 0
        }

    /**
     * Returns the "logical length" of this `SparseBitSet`: the index
     * of the highest set bit in the `SparseBitSet` plus one. Returns
     * zero if the `SparseBitSet` contains no set bits.
     *
     * @return      the logical length of this SparseBitSet
     * @since       1.6
     */
    fun length(): Int {
        statisticsUpdate()
        return cache!!.length
    }

    /**
     * Returns the index of the first bit that is set to `false` that
     * occurs on or after the specified starting index.
     *
     * @param       i the index to start checking from (inclusive)
     * @return      the index of the next clear bit, or -1 if there is no such bit
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * @since       1.6
     */
    fun nextClearBit(i: Int): Int {
        /*  The index of this method is permitted to be Integer.MAX_VALUE, as this
            is needed to make this method work together with the method
            nextSetBit()--as might happen if a search for the next clear bit is
            started after finding a set bit labelled Integer.MAX_VALUE-1. This
            case is not optimised, the code will eventually return -1 (since
            the Integer.MAX_VALUEth bit does "exist," and is 0. */

        if (i < 0) throw IndexOutOfBoundsException("i=$i")
        /*  This is the word from which the search begins. */
        var w = i shr SHIFT3
        var w3 = w and MASK3
        var w2 = (w shr SHIFT2) and MASK2
        var w1 = w shr SHIFT1

        var nword = 0L.inv() shl i
        val aLength = bits!!.size

        var a2: Array<LongArray?>? = null
        var a3: LongArray?= null
        /*  Is the next clear bit in the same word at the nominated beginning bit
        (including the nominated beginning bit itself). The first check is
        whether the starting bit is within the structure at all. */
        if (w1 < aLength && (bits[w1].also { a2 = it }) != null && (a2!![w2].also {
                a3 = it
            }) != null && (((a3!![w3].inv() and (0L.inv() shl i)).also { nword = it })) == 0L) {
            /*  So now start a search though the rest of the entries for
                a null area or block, or a clear bit (a set bit in the
                complemented value). */
            ++w
            w3 = w and MASK3
            w2 = (w shr SHIFT2) and MASK2
            w1 = w shr SHIFT1
            nword = 0L.inv()
            loop@ while (w1 != aLength) {
                if ((bits[w1].also { a2 = it }) == null) break
                while (w2 != LENGTH2) {
                    if ((a2!![w2].also { a3 = it }) == null) break@loop
                    while (w3 != LENGTH3) {
                        if ((a3!![w3].inv().also { nword = it }) != 0L) break@loop
                        ++w3
                    }
                    w3 = 0
                    ++w2
                }
                w3 = 0
                w2 = w3
                ++w1
            }
        }
        val result: Int = ((((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) +nword.countTrailingZeroBits()) //Long.numberOfTrailingZeros(nword))
        return (if (result == Int.MAX_VALUE) -1 else result)
    }

    /**
     * Returns the index of the first bit that is set to `true` that
     * occurs on or after the specified starting index. If no such it exists then
     * -1 is returned.
     *
     *
     * To iterate over the `true` bits in a `SparseBitSet
     * sbs`, use the following loop:
     *
     * <pre>
     * for( int i = sbbits.nextSetBit(0); i &gt;= 0; i = sbbits.nextSetBit(i+1) )
     * {
     * // operate on index i here
     * }</pre>
     *
     * @param       i the index to start checking from (inclusive)
     * @return      the index of the next set bit
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * @since       1.6
     */
    fun nextSetBit(i: Int): Int {
        /*  The index value (i) of this method is permitted to be Integer.MAX_VALUE,
            as this is needed to make the loop defined above work: just in case the
            bit labelled Integer.MAX_VALUE-1 is set. This case is not optimised:
            but eventually -1 will be returned, as this will be included with
            any search that goes off the end of the level1 array. */

        if (i < 0) throw IndexOutOfBoundsException("i=$i")
        /*  This is the word from which the search begins. */
        var w = i shr SHIFT3
        var w3 = w and MASK3
        var w2 = (w shr SHIFT2) and MASK2
        var w1 = w shr SHIFT1

        var word = 0L
        val aLength = bits.size

        var a2: Array<LongArray?>? =null
        var a3: LongArray? =null
        /*  Is the next set bit in the same word at the nominated beginning bit
        (including the nominated beginning bit itself). The first check is
        whether the starting bit is within the structure at all. */
        if (w1 < aLength && ((bits[w1].also { a2 = it }) == null || (a2!![w2].also {
                a3 = it
            }) == null || (((a3!![w3] and (0L.inv() shl i)).also { word = it }) == 0L))) {
            /*  So now start a search though the rest of the entries for a bit. */
            ++w
            w3 = w and MASK3
            w2 = (w shr SHIFT2) and MASK2
            w1 = w shr SHIFT1
            major@ while (w1 != aLength) {
                if ((bits[w1].also { a2 = it }) != null) while (w2 != LENGTH2) {
                    if ((a2!![w2].also { a3 = it }) != null) while (w3 != LENGTH3) {
                        if ((a3!![w3].also { word = it }) != 0L) break@major
                        ++w3
                    }
                    w3 = 0
                    ++w2
                }
                w3 = 0
                w2 = w3
                ++w1
            }
        }
        return (if (w1 >= aLength)
            -1
        else
            ((((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) +word.countTrailingZeroBits())) // Long.numberOfTrailingZeros(word)))
    }

    /**
     * Returns the index of the nearest bit that is set to `false`
     * that occurs on or before the specified starting index.
     * If no such bit exists, or if `-1` is given as the
     * starting index, then `-1` is returned.
     *
     * @param  i the index to start checking from (inclusive)
     * @return the index of the previous clear bit, or `-1` if there
     * is no such bit
     * @throws IndexOutOfBoundsException if the specified index is less
     * than `-1`
     * @since  1.2
     * @see java.util.BitSet.previousClearBit
     */
    fun previousClearBit(i: Int): Int {
        if (i < 0) {
            if (i == -1) return -1
            throw IndexOutOfBoundsException("i=$i")
        }

        val bits = this.bits
        val aSize = bits!!.size - 1

        val w = i shr SHIFT3
        var w3 = w and MASK3
        var w2 = (w shr SHIFT2) and MASK2
        var w1 = w shr SHIFT1
        if (w1 > aSize) return i

        var w4 = i % LENGTH4

        var word: Long
        var a2: Array<LongArray?>? = null
        var a3: LongArray? = null

        while (w1 >= 0) {
            if ((bits[w1].also {
                    a2 = it
                }) == null) return (((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) + w4
            while (w2 >= 0) {
                if ((a2!![w2].also {
                        a3 = it
                    }) == null) return (((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) + w4
                while (w3 >= 0) {
                    if ((a3!![w3].also {
                            word = it
                        }) == 0L) return (((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) + w4
                    for (bitIdx in w4 downTo 0) {
                        if ((word and (1L shl bitIdx)) == 0L) return (((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) + bitIdx
                    }
                    w4 = LENGTH4_SIZE
                    --w3
                }
                w3 = LENGTH3_SIZE
                --w2
            }
            w2 = LENGTH2_SIZE
            --w1
        }
        return -1
    }

    /**
     * Returns the index of the nearest bit that is set to `true`
     * that occurs on or before the specified starting index.
     * If no such bit exists, or if `-1` is given as the
     * starting index, then `-1` is returned.
     *
     * @param  i the index to start checking from (inclusive)
     * @return the index of the previous set bit, or `-1` if there
     * is no such bit
     * @throws IndexOutOfBoundsException if the specified index is less
     * than `-1`
     * @since  1.2
     * @see java.util.BitSet.previousSetBit
     */
    fun previousSetBit(i: Int): Int {
        if (i < 0) {
            if (i == -1) return -1
            throw IndexOutOfBoundsException("i=$i")
        }

        val bits = this.bits
        val aSize = bits.size - 1

        /*  This is the word from which the search begins. */
        val w = i shr SHIFT3
        var w1 = w shr SHIFT1
        var w2: Int
        var w3: Int
        var w4: Int
        /*  But if its off the end of the array, start from the very end. */
        if (w1 > aSize) {
            w1 = aSize
            w2 = LENGTH2_SIZE
            w3 = LENGTH3_SIZE
            w4 = LENGTH4_SIZE
        } else {
            w2 = (w shr SHIFT2) and MASK2
            w3 = w and MASK3
            w4 = i % LENGTH4
        }
        var word: Long
        var a2: Array<LongArray?>?=null
        var a3: LongArray?=null
        while (w1 >= 0) {
            if ((bits[w1].also { a2 = it }) != null) while (w2 >= 0) {
                if ((a2!![w2].also { a3 = it }) != null) while (w3 >= 0) {
                    if ((a3!![w3].also { word = it }) != 0L) for (bitIdx in w4 downTo 0) {
                        if ((word and (1L shl bitIdx)) != 0L) return (((w1 shl SHIFT1) + (w2 shl SHIFT2) + w3) shl SHIFT3) + bitIdx
                    }
                    w4 = LENGTH4_SIZE
                    --w3
                }
                w3 = LENGTH3_SIZE
                w4 = LENGTH4_SIZE
                --w2
            }
            w2 = LENGTH2_SIZE
            w3 = LENGTH3_SIZE
            w4 = LENGTH4_SIZE
            --w1
        }
        return -1
    }

    /**
     * Performs a logical **OR** of the addressed target bit with the
     * argument value. This bit set is modified so that the addressed bit has the
     * value `true` if and only if it both initially had the value
     * `true` or the argument value is `true`.
     *
     * @param       i a bit index
     * @param       value a boolean value to OR with that bit
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun or(i: Int, value: Boolean) {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        if (value) set(i)
    }

    /**
     * Performs a logical **OR** of the addressed target bit with the
     * argument value within the given range. This bit set is modified so that
     * within the range a bit in it has the value `true` if and only if
     * it either already had the value `true` or the corresponding bit
     * in the bit set argument has the value `true`. Outside the range
     * this set is not changed.
     *
     * @param       i index of the first bit to be included in the operation
     * @param       j index after the last bit to included in the operation
     * @param       b the SparseBitSet with which to perform the **OR**
     * operation with this SparseBitSet
     * @exception   IndexOutOfBoundsException if `i` is negative or
     * equal to Integer.MAX_VALUE, or `j` is negative,
     * or `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun or(i: Int, j: Int, b: SparseBitSet?) {
        setScanner(i, j, b, orStrategy)
    }

    /**
     * Performs a logical **OR** of this bit set with the bit set argument.
     * This bit set is modified so that a bit in it has the value `true`
     * if and only if it either already had the value `true` or the
     * corresponding bit in the bit set argument has the value `true`.
     *
     * @param       b the SparseBitSet with which to perform the **OR**
     * operation with this SparseBitSet
     * @since       1.6
     */
    fun or(b: SparseBitSet) {
        setScanner(0, b.bitsLength, b, orStrategy)
    }

    /**
     * Sets the bit at the specified index.
     *
     * @param       i a bit index
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun set(i: Int) {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        val w = i shr SHIFT3
        val w1 = w shr SHIFT1
        val w2 = (w shr SHIFT2) and MASK2

        if (i >= bitsLength) resize(i)
        var a2: Array<LongArray?>?
        if ((bits[w1].also { a2 = it }) == null) {
            bits[w1] = arrayOfNulls(LENGTH2)
            a2 = bits[w1]
        }
        var a3: LongArray?
        if ((a2!![w2].also { a3 = it }) == null) {
            a2!![w2] = LongArray(LENGTH3)
            a3 = a2!![w2]
        }
        a3!![w and MASK3] = a3!![w and MASK3] or (1L shl i)
        cache!!.hash = 0 //Invalidate size, etc., scan
    }

    /**
     * Sets the bit at the specified index to the specified value.
     *
     * @param       i a bit index
     * @param       value a boolean value to set
     * @exception   IndexOutOfBoundsException if the specified index is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun set(i: Int, value: Boolean) {
        if (value) set(i)
        else clear(i)
    }

    /**
     * Sets the bits from the specified `i` (inclusive) to the specified
     * `j` (exclusive) to `true`.
     *
     * @param       i index of the first bit to be set
     * @param       j index after the last bit to be se
     * @exception   IndexOutOfBoundsException if `i` is negative or is
     * equal to Integer.MAX_INT, or `j` is negative, or
     * `i` is larger than `j`.
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun set(i: Int, j: Int) {
        setScanner(i, j, null, setStrategy)
    }

    /**
     * Sets the bits from the specified `i` (inclusive) to the specified
     * `j` (exclusive) to the specified value.
     *
     * @param       i index of the first bit to be set
     * @param       j index after the last bit to be set
     * @param       value to which to set the selected bits
     * @exception   IndexOutOfBoundsException if `i` is negative or is
     * equal to Integer.MAX_VALUE, or `j` is negative, or
     * `i` is larger than `j`
     * @since       1.6
     */
    fun set(i: Int, j: Int, value: Boolean) {
        if (value) set(i, j)
        else clear(i, j)
    }

    /**
     * Returns the number of bits of space nominally in use by this
     * `SparseBitSet` to represent bit values. The count of bits in
     * the set is the (label of the last set bit) + 1 - (the label of the first
     * set bit).
     *
     * @return      the number of bits (true and false) nominally in this bit set
     * at this moment
     * @since       1.6
     */
    fun size(): Int {
        statisticsUpdate()
        return cache!!.size
    }

    /**
     * Determine, and create a String with the bit set statistics. The statistics
     * include: Size, Length, Cardinality, Total words (*i.e.*, the total
     * number of 64-bit "words"), Set array length (*i.e.*, the number of
     * references that can be held by the top level array, Level2 areas in use,
     * Level3 blocks in use,, Level2 pool size, Level3 pool size, and the
     * Compaction count.
     *
     *
     * This method is intended for diagnostic use (as it is relatively expensive
     * in time), but can be useful in understanding an application's use of a
     * `SparseBitSet`.
     *
     * @param       values an array for the individual results (if not null)
     * @return      a String detailing the statistics of the bit set
     * @since       1.6
     */
    /**
     * Convenience method for statistics if the individual results are not needed.
     *
     * @return      a String detailing the statistics of the bit set
     * @see .statistics
     * @since       1.6
     */
    @JvmOverloads
    fun statistics(values: Array<String?>? = null): String {
        statisticsUpdate() //  Ensure statistics are up-to-date
        val v = arrayOfNulls<String>(Statistics.entries.size)

        /*  Assign the statistics values to the appropriate entry. The order
            of the assignments does not matter--the ordinal serves to get the
            values into the matching order with the labels from the enumeration. */
        v[Statistics.Size.ordinal] = size().toString()
        v[Statistics.Length.ordinal] = length().toString()
        v[Statistics.Cardinality.ordinal] = cardinality().toString()
        v[Statistics.Total_words.ordinal] = cache!!.count.toString()
        v[Statistics.Set_array_length.ordinal] = bits!!.size.toString()
        v[Statistics.Set_array_max_length.ordinal] = MAX_LENGTH1.toString()
        v[Statistics.Level2_areas.ordinal] = cache!!.a2Count.toString()
        v[Statistics.Level2_area_length.ordinal] = LENGTH2.toString()
        v[Statistics.Level3_blocks.ordinal] = cache!!.a3Count.toString()
        v[Statistics.Level3_block_length.ordinal] = LENGTH3.toString()
        v[Statistics.Compaction_count_value.ordinal] = compactionCount.toString()

        /*  Determine the longest label, so that the equal signs may be lined-up. */
        var longestLabel = 0
        for (s in Statistics.entries) longestLabel =
            max(longestLabel.toDouble(), s.name.length.toDouble()).toInt()

        /*  Build a String that has for each statistic, the name of the statistic,
            padding, and equals sign, and the value. The "Load_factor_value",
            "Average_length_value", and "Average_chain_length" are printed as
            floating point values. */
        val result: StringBuilder = StringBuilder()
        for (s in Statistics.entries) {
            result.append(s.name) // The name of the statistic
            for (i in 0 until longestLabel - s.name.length) result.append(' ') //  Fill out the field

            result.append(" = ") //  Show an equals sign
            result.append(v[s.ordinal]) // and a value
            result.append('\n')
        }
        /*  Remove the underscores. */
        for (i in 0 until result.length) if (result.get(i) == '_') result.set(i, ' ')

        if (values != null) {
            val len = min(values.size.toDouble(), v.size.toDouble()).toInt()
            arraycopy(v, 0, values, 0, len)
        }
        return result.toString()
    }

    /**
     * Returns a string representation of this bit set. For every index for which
     * this `SparseBitSet` contains a bit in the set state, the decimal
     * representation of that index is included in the result. Such indices are
     * listed in order from lowest to highest. If there is a subsequence of set
     * bits longer than the value given by toStringCompaction, the subsequence
     * is represented by the value for the first and the last values, with ".."
     * between them. The individual bits, or the representation of sub-sequences
     * are separated by ",&nbsp;" (a comma and a space) and surrounded by braces,
     * resulting in a compact string showing (a variant of) the usual mathematical
     * notation for a set of integers.
     * <br></br>
     * Example (with the default value of 2 for subsequences):
     * <pre>
     * SparseBitSet drPepper = new SparseBitSet();
    </pre> *
     * Now `drPepper.toString()` returns "`{}`".
     * <br></br>
     * <pre>
     * drPepper.set(2);
    </pre> *
     * Now `drPepper.toString()` returns "`{2}`".
     * <br></br>
     * <pre>
     * drPepper.set(3, 4);
     * drPepper.set(10);
    </pre> *
     * Now `drPepper.toString()` returns "`{2..4, 10}`".
     * <br></br>
     * This method is intended for diagnostic use (as it is relatively expensive
     * in time), but can be useful in interpreting problems in an application's use
     * of a `SparseBitSet`.
     *
     * @return      a String representation of this SparseBitSet
     * @see .toStringCompaction
     * @since       1.6
     */
    override fun toString(): String {
        val p: StringBuilder = StringBuilder(200)
        p.append('{')
        var i = nextSetBit(0)
        /*  Loop so long as there is another bit to append to the String. */
        while (i >= 0) {
            /*  Append that next bit */
            p.append(i)
            /*  Find the position of the next bit to show. */
            var j = nextSetBit(i + 1)
            if (compactionCount > 0) {
                /*  Give up if there is no next bit to show. */
                if (j < 0) break
                /*  Find the next clear bit is after the current bit, i.e., i */
                var last = nextClearBit(i)
                /*  Compute the position of the next clear bit after the current
                    subsequence of set bits. */
                last = (if (last < 0) Int.MAX_VALUE else last)
                /*  If the subsequence is more than the specified bits long, then
                    collapse the subsequence into one entry in the String. */
                if (i + compactionCount < last) {
                    p.append("..").append(last - 1)
                    /*  Having accounted for a subsequence of bits that are all set,
                        recompute the label of the next bit to show. */
                    j = nextSetBit(last)
                }
            }
            /*  If there is another set bit, put a comma and a space after the
                last entry in the String.  */
            if (j >= 0) p.append(", ")
            /*  Transfer to i the index of the next set bit. */
            i = j
        }
        /*  Terminate the representational String, and return it. */
        p.append('}')
        return p.toString()
    }

    /** Sequences of set bits longer than this value are shown by
     * [.toString] as a "sub-sequence," in the form `a..b`.
     * Setting this value to zero causes each set bit to be listed individually.
     * The default default value is 2 (which means sequences of three or more
     * bits set are shown as a subsequence, and all other set bits are listed
     * individually).
     *
     *
     * Note: this value will be passed to `SparseBitSet`s that
     * may be created within or as a result of the operations on this bit set,
     * or, for static methods, from the value belonging to the first parameter.
     *
     * @param       count the maximum count of a run of bits that are shown as
     * individual entries in a `toString`() conversion.
     * If 0, all bits are shown individually.
     * @since       1.6
     * @see .toString
     */
    fun toStringCompaction(count: Int) {
        compactionCount = count
    }

    /**
     * If *change* is `true`, the current value of the
     * *toStringCompaction*() value is made the default value for all
     * `SparseBitSet`s created from this point onward in this JVM.
     *
     * @param       change if true, change the default value
     * @since       1.6
     */
    fun toStringCompaction(change: Boolean) {
        /*  This is an assignment to a static value: the integer value assignment
            is atomic, so there will not be a partial store. If multiple
            invocations are made from multiple threads, there is a race
            condition that cannot be resolved by synchronization. */
        if (change) compactionCountDefault = compactionCount
    }

    /**
     * Performs a logical **XOR** of the addressed target bit with the
     * argument value. This bit set is modified so that the addressed bit has the
     * value `true` if and only one of the following statements holds:
     *
     *  * The addressed bit initially had the value `true`, and the
     * value of the argument is `false`.
     *  * The bit initially had the value `false`, and the
     * value of the argument is `true`.
     *
     *
     * @param       i a bit index
     * @param       value a boolean value to **XOR** with that bit
     * @exception   IndexOutOfBoundsException if the specified index
     * is negative
     * or equal to Integer.MAX_VALUE
     * @since       1.6
     */
    fun xor(i: Int, value: Boolean) {
        if ((i + 1) < 1) throw IndexOutOfBoundsException("i=$i")
        if (value) flip(i)
    }

    /**
     * Performs a logical **XOR** of this bit set with the bit set argument
     * within the given range. This resulting bit set is computed so that a bit
     * within the range in it has the value `true` if and only if one
     * of the following statements holds:
     *
     *  * The bit initially had the value `true`, and the
     * corresponding bit in the argument set has the value `false`.
     *  * The bit initially had the value `false`, and the
     * corresponding bit in the argument set has the value `true`.
     *
     * Outside the range this set is not changed.
     *
     * @param       i index of the first bit to be included in the operation
     * @param       j index after the last bit to included in the operation
     * @param       b the SparseBitSet with which to perform the **XOR**
     * operation with this SparseBitSet
     * @exception   IndexOutOfBoundsException if `i` is negative or
     * equal to Integer.MAX_VALUE, or `j` is negative,
     * or `i` is larger than `j`
     * @since       1.6
     */
    @Throws(IndexOutOfBoundsException::class)
    fun xor(i: Int, j: Int, b: SparseBitSet?) {
        setScanner(i, j, b, xorStrategy)
    }

    /**
     * Performs a logical **XOR** of this bit set with the bit set argument.
     * This resulting bit set is computed so that a bit in it has the value
     * `true` if and only if one of the following statements holds:
     *
     *  * The bit initially had the value `true`, and the
     * corresponding bit in the argument set has the value `false`.
     *  * The bit initially had the value `false`, and the
     * corresponding bit in the argument set has the value `true`.
     *
     *
     * @param       b the SparseBitSet with which to perform the **XOR**
     * operation with thisSparseBitSet
     * @since       1.6
     */
    fun xor(b: SparseBitSet) {
        setScanner(0, b.bitsLength, b, xorStrategy)
    }

    /**
     * Intializes all the additional objects required for correct operation.
     *
     * @since       1.6
     */
    protected fun constructorHelper() {
        spare = LongArray(LENGTH3)
        cache = Cache()
        updateStrategy = UpdateStrategy()
    }

    /**
     * Clear out a part of the set array with nulls, from the given start to the
     * end of the array. If the given parameter is beyond the end of the bits
     * array, nothing is changed.
     *
     * @param       start word index at which to start (inclusive)
     * @since       1.6
     */
    protected fun nullify(start: Int) {
        val aLength = bits.size
        if (start < aLength) {
            for (w in start until aLength) bits[w] = null
            cache!!.hash = 0 //  Invalidate size, etc., values
        }
    }

    /**
     * Resize the bit array. Moves the entries in the the bits array of this
     * SparseBitSet into an array whose size (which may be larger or smaller) is
     * the given bit size (*i.e.*, includes the bit whose index is one less
     * that the given value). If the new array is smaller, the excess entries in
     * the set array are discarded. If the new array is bigger, it is filled with
     * nulls.
     *
     * @param       index the desired address to be included in the set
     * @since       1.6
     */
    protected fun resize(index: Int) {
        /*  Find an array size that is a power of two that is as least as large
            enough to contain the index requested. */
        val w1 = (index shr SHIFT3) shr SHIFT1
        var newSize: Int = w1.takeHighestOneBit() //Integer.highestOneBit(w1)
        if (newSize == 0) newSize = 1
        if (w1 >= newSize) newSize = newSize shl 1
        if (newSize > MAX_LENGTH1) newSize = MAX_LENGTH1
        val aLength1 = (if (bits != null) bits.size else 0)

        if (newSize != aLength1 || bits == null) { // only if the size needs to be changed
            val temp: Array<Array<LongArray?>?> = arrayOfNulls(newSize) //  Get the new array
            if (aLength1 != 0) {
                /*  If it exists, copy old array to the new array. */
                arraycopy(
                    bits,
                    0,
                    temp,
                    0,
                    min(aLength1, newSize)
                )
                nullify(0) //  Don't leave unused pointers around. */
            }
            bits = temp //  Set new array as the set array

             //  Index of last possible bit, plus one.
            bitsLength = (if (newSize == MAX_LENGTH1) Int.MAX_VALUE else newSize * UNIT)
        }
    }

    /**
     * Scans over the bit set (and a second bit set if part of the operation) are
     * all performed by this method. The properties and the operation executed
     * are defined by a given strategy, which must be derived from the
     * `AbstractStrategy`. The strategy defines how to operate on a
     * single word, and on whole words that may or may not constitute a full
     * block of words.
     *
     * @param       i the bit (inclusive) at which to start the scan
     * @param       j the bit (exclusive) at which to stop the scan
     * @param       b a SparseBitSet, if needed, the second SparseBitSet in the
     * operation
     * @param       op the AbstractStrategy class defining the operation to be
     * executed
     * @exception   IndexOutOfBoundsException
     * @since       1.6
     * @see AbstractStrategy
     */
    @Throws(IndexOutOfBoundsException::class)
    protected fun setScanner(
        i: Int, j: Int, b: SparseBitSet?,
        op: AbstractStrategy,
    ) {
        /*  This method has been assessed as having a McCabe cyclomatic
            complexity of 47 (i.e., impossibly high). However, given that this
            method incorporates all the set scanning logic for all methods
            (with the exception of nextSetBit and nextClearBit, which themselves
            have high cyclomatic complexities of 13), and is attempting to minimise
            execution time (hence deals with processing shortcuts), it cannot be
            expected to be simple. In fact, the work of lining up level3 blocks
            proceeds step-wise, and each sub-section piece is reasonably
            straight-forward. Nevertheless, the number of paths is high, and
            caution is advised in attempting to correct anything. */

        /*  Do whatever the strategy needs to get started, and do whatever initial
            checking is needed--fail here if needed before much else is done. */

        var i = i
        if (b!=null && op.start(b)) cache!!.hash = 0

        if (j < i || (i + 1) < 1) throwIndexOutOfBoundsException(i, j)
        if (i == j) return

        /*  Get the values of all the short-cut options. */
        val properties = op.properties()
        val f_op_f_eq_f = (properties and AbstractStrategy.F_OP_F_EQ_F) != 0
        val f_op_x_eq_f = (properties and AbstractStrategy.F_OP_X_EQ_F) != 0
        val x_op_f_eq_f = (properties and AbstractStrategy.X_OP_F_EQ_F) != 0
        val x_op_f_eq_x = (properties and AbstractStrategy.X_OP_F_EQ_X) != 0

        /*  Index of the current word, and mask for the first word,
            to be processed in the bit set. */
        var u = i shr SHIFT3
        val um = 0L.inv() shl i

        /*  Index of the final word, and mask for the final word,
            to be processed in the bit set. */
        val v = (j - 1) shr SHIFT3
        val vm = 0L.inv() ushr -j

        /*  Set up the two bit arrays (if the second exists), and their
            corresponding lengths (if any). */
        var a1 = bits //  Level1, i.e., the bit arrays
        var aLength1 = bits.size
        val b1: Array<Array<LongArray?>?>? = (b?.bits)
        val bLength1 = (if (b1 != null) b.bits.size else 0)

        /*  Calculate the initial values of the parts of the words addresses,
            as well as the location of the final block to be processed.  */
        var u1 = u shr SHIFT1
        var u2 = (u shr SHIFT2) and MASK2
        var u3 = u and MASK3
        val v1 = v shr SHIFT1
        val v2 = (v shr SHIFT2) and MASK2
        val v3 = v and MASK3
        val lastA3Block = (v1 shl LEVEL2) + v2

        /*  Initialize the local copies of the counts of blocks and areas; and
            whether there is a partial first block.  */
        var a2CountLocal = 0
        var a3CountLocal = 0
        var notFirstBlock = u == 0 && um == 0L.inv()

        /*  The first level2 is cannot be judged empty if not being scanned from
            the beginning. */
        var a2IsEmpty = u2 == 0 //  Presumption
        while (i < j) {
            /*  Determine if there is a level2 area in both the a and the b set,
                and if so, set the references to these areas. */
            var a2: Array<LongArray?>? = null
            var haveA2 = u1 < aLength1 && (a1[u1].also { a2 = it }) != null
            var b2: Array<LongArray?>? = null
            val haveB2 = u1 < bLength1 && b1 != null && (b1[u1].also { b2 = it }) != null
            /*  Handling of level 2 empty areas: determined by the
                properties of the strategy. It is necessary to actually visit
                the first and last blocks of a scan, since not all of the block
                might participate in the operation, hence making decision based
                on just the references to the blocks could be wrong. */
            if ((!haveA2 && !haveB2 && f_op_f_eq_f || !haveA2 && f_op_x_eq_f || !haveB2 && x_op_f_eq_f)
                && notFirstBlock && u1 != v1
            ) { //nested if!
                if (u1 < aLength1) a1[u1] = null
            } else {
                val limit2 = (if (u1 == v1) v2 + 1 else LENGTH2)
                while (u2 != limit2) {
                    /*  Similar logic applied here as for the level2 blocks.
                        The initial and final block must be examined. In other
                        cases, it may be possible to make a decision based on
                        the value of the references, as indicated by the
                        properties of the strategy. */
                    var a3: LongArray? = null
                    val haveA3 = haveA2 && (a2!![u2].also { a3 = it }) != null
                    var b3: LongArray? = null
                    val haveB3 = haveB2 && (b2!![u2].also { b3 = it }) != null
                    val a3Block = (u1 shl LEVEL2) + u2
                    val notLastBlock = lastA3Block != a3Block
                    /*  Handling of level 3 empty areas: determined by the
                        properties of the strategy. */
                    if ((!haveA3 && !haveB3 && f_op_f_eq_f || !haveA3 && f_op_x_eq_f || !haveB3 && x_op_f_eq_f)
                        && notFirstBlock && notLastBlock
                    ) {
                        /*  Do not need level3 block, so remove it, and move on. */
                        if (haveA2) a2!![u2] = null
                    } else {
                        /*  So what is needed is the level3 block. */
                        val base3 = a3Block shl SHIFT2
                        val limit3 = (if (notLastBlock) LENGTH3 else v3)
                        if (!haveA3) a3 = spare
                        if (!haveB3) b3 = ZERO_BLOCK
                        var isZero: Boolean
                        if (notFirstBlock && notLastBlock) isZero =
                            if (x_op_f_eq_x && !haveB3) op.isZeroBlock(a3)
                            else op.block(base3, 0, LENGTH3, a3!!, b3!!)
                        else { /*  Partial block to process. */
                            if (notFirstBlock) {
                                /*  By implication, this is the last block */
                                isZero = op.block(base3, 0, limit3, a3!!, b3!!)
                                //  Do the whole words
                                isZero = isZero and op.word(base3, limit3, a3!!, b3!!, vm)
                                //  And then the final word
                            } else { // u, v are correct if first block
                                if (u == v)  //  Scan starts and ends in one word
                                    isZero = op.word(base3, u3, a3!!, b3!!, um and vm)
                                else { // Scan starts in this a3 block
                                    isZero = op.word(base3, u3, a3!!, b3!!, um)
                                    //  First word
                                    isZero = isZero and
                                            op.block(base3, u3 + 1, limit3, a3!!, b3!!)
                                    //  Remainder of full words in block
                                    if (limit3 != LENGTH3) isZero =
                                        isZero and op.word(base3, limit3, a3!!, b3!!, vm)
                                    //  If there is a partial word left
                                }
                                notFirstBlock = true //  Only one first block
                            }
                            if (isZero) isZero = op.isZeroBlock(a3)
                            // If not known to have a non-zero
                            // value, be sure whether all zero.
                        }
                        if (isZero)  //  The resulting a3 block has no values
                        { // nested if!
                            /*  If there is an level 2 area make the entry for this
                                level3 block be a null (i.e., remove any a3 block ). */
                            if (haveA2) a2!![u2] = null
                        } else {
                            /*  If the a3 block used was the spare block, put it
                                into current level2 area; get a new spare block. */
                            if (a3 == spare) {
                                if (i >= bitsLength)  //Check that the set is large
                                { //  enough to take the new block
                                    resize(i) //  Make it large enough
                                    a1 = bits //  Update reference and length
                                    aLength1 = a1!!.size
                                }
                                if (a2 == null)  //  Ensure a level 2 area
                                {
                                    a2 = arrayOfNulls(LENGTH2)
                                    a1!![u1] = a2
                                    haveA2 = true //  Ensure know level2 not empty
                                }
                                a2!![u2] = a3 //  Insert the level3 block
                                spare = LongArray(LENGTH3) // Replace the spare
                            }
                            ++a3CountLocal // Count the level 3 block
                        }
                        a2IsEmpty = a2IsEmpty and !(haveA2 && a2!![u2] != null)
                    } //  Keep track of level 2 usage

                    ++u2
                    u3 = 0
                } /* end while ( u2 != limit2 ) */
                /*  If the loop finishes without completing the level 2, it may
                    be left with a reference but still be all null--this is OK. */
                if (u2 == LENGTH2 && a2IsEmpty && u1 < aLength1) a1!![u1] = null
                else ++a2CountLocal //  Count level 2 areas
            }
            /*  Advance the value of u based on what happened. */
            i = ((++u1 shl SHIFT1).also { u = it }) shl SHIFT3
            u2 = 0 //  u3 = 0
            //  Compute next word and bit index
            if (i < 0) i = Int.MAX_VALUE //  Don't go over the end
        } /* end while( i < j ) */

        /*  Do whatever the strategy needs in order to finish. */
        op.finish(a2CountLocal, a3CountLocal)
    }

    /**
     * The entirety of the bit set is examined, and the various statistics of
     * the bit set (size, length, cardinality, hashCode, etc.) are computed. Level
     * arrays that are empty (i.e., all zero at level 3, all null at level 2) are
     * replaced by null references, ensuring a normalized representation.
     *
     * @since       1.6
     */
    protected fun statisticsUpdate() {
        if (cache!!.hash != 0) return
        setScanner(0, bitsLength, null, updateStrategy)
    }

    //==============================================================================
    //  Serialization/Deserialization methods
    //==============================================================================
    /**
     * Save the state of the `SparseBitSet` instance to a stream
     * (*i.e.*, serialize it).
     *
     * @param       s the ObjectOutputStream to which to write the serialized object
     * @exception   IOException if an io error occurs
     * @exception   InternalError if the SparseBitSet representation is
     * inconsistent
     *
     * @serialData  The default data is emitted, followed by the current
     * *compactionCount* for the bit set, and then the
     * *length* of the set (the position of the last bit),
     * followed by the *cache.count* value (an `int`,
     * the number of `int->long` pairs needed to describe
     * the set), followed by the index (`int`) and word
     * (`long`) for each `int->long` pair.
     * The mappings need not be emitted in any particular order. This
     * is followed by the *hashCode* for the set that can be used
     * as an integrity check when the bit set is read back.
     *
     * @since       1.6
     */
//    @Throws(IOException::class, InternalError::class)
//    private fun writeObject(s: ObjectOutputStream) {
//        statisticsUpdate() //  Update structure and stats if needed.
//        /*  Write any hidden stuff. */
//        s.defaultWriteObject()
//        s.writeInt(compactionCount) //  Needed to preserve value
//        s.writeInt(cache!!.length) //  Needed to know where last bit is
//
//        /*  This is the number of index/value pairs to be written. */
//        var count = cache!!.count //  Minimum number of words to be written
//        s.writeInt(count)
//        val a1 = bits
//        val aLength1 = a1!!.size
//        var a2: Array<LongArray>
//        var a3: LongArray
//        var word: Long
//        for (w1 in 0 until aLength1) if ((a1[w1].also {
//                a2 = it
//            }) != null) for (w2 in 0 until LENGTH2) if ((a2[w2].also { a3 = it }) != null) {
//            val base = (w1 shl SHIFT1) + (w2 shl SHIFT2)
//            for (w3 in 0 until LENGTH3) if ((a3[w3].also { word = it }) != 0L) {
//                s.writeInt(base + w3)
//                s.writeLong(word)
//                --count
//            }
//        }
//        if (count != 0) throw InternalError("count of entries not consistent")
//        /*  As a consistency check, write the hash code of the set. */
//        s.writeInt(cache!!.hash)
//    }

    /**
     * Reconstitute the `SparseBitSet` instance from a stream
     * (*i.e.*, deserialize it).
     *
     * @param       s the ObjectInputStream to use
     * @exception   IOException if there is an io error
     * @exception   ClassNotFoundException if the stream contains an unidentified
     * class
     * @since       1.6
     */
//    @Throws(IOException::class, ClassNotFoundException::class)
//    private fun readObject(s: ObjectInputStream) {
//        /* Read in any hidden stuff that is part of the class overhead. */
//        s.defaultReadObject()
//        compactionCount = s.readInt()
//        val aLength: Int = s.readInt()
//        resize(aLength) // Make sure there is enough space
//
//        /* Read in number of mappings. */
//        val count: Int = s.readInt()
//        /*  Read the keys and values, them into the set array, areas, and blocks. */
//        var a2: Array<LongArray?>?
//        var a3: LongArray?
//        for (n in 0 until count) {
//            val w: Int = s.readInt()
//            val w3 = w and MASK3
//            val w2 = (w shr SHIFT2) and MASK2
//            val w1 = w shr SHIFT1
//
//            val word: Long = s.readLong()
//            if ((bits!![w1].also { a2 = it }) == null) {
//                bits!![w1] = arrayOfNulls(LENGTH2)
//                a2 = bits!![w1]
//            }
//            if ((a2!![w2].also { a3 = it }) == null) {
//                a2!![w2] = LongArray(LENGTH3)
//                a3 = a2!![w2]
//            }
//            a3!![w3] = word
//        }
//        /* Ensure all the pieces are set up for set scanning. */
//        constructorHelper()
//        statisticsUpdate()
//        if (count != cache!!.count) throw InternalError("count of entries not consistent")
//        val hash: Int = s.readInt() //  Get the hashcode that was stored
//        if (hash != cache!!.hash)  //  An error of some kind if not the same
//            throw IOException("deserialized hashCode mis-match")
//    }

    //=============================================================================
    //  Statistics enumeration
    //=============================================================================
    /**
     * These enumeration values are used as labels for the values in the String
     * created by the *statistics*() method. The values of the corresponding
     * statistics are `int`s, except for the loadFactor and
     * Average_chain_length values, which are `float`s.
     *
     *
     * An array of `String`s may be obtained containing a
     * representation of each of these values. An element of such an array, say,
     * `values`, may be accessed, for example, by:
     * <pre>
     * values[SparseBitSet.statistics.Buckets_available.ordinal()]</pre>
     *
     * @see .statistics
     */
    enum class Statistics {
        /**
         * The size of the bit set, as give by the *size*() method.
         */
        Size,  // 0

        /**
         * The length of the bit set, as give by the *length*() method.
         */
        Length,  // 1

        /**
         * The cardinality of the bit set, as give by the *cardinality*() method.
         */
        Cardinality,  // 2

        /**
         * The total number of non-zero 64-bits "words" being used to hold the
         * representation of the bit set.
         */
        Total_words,  // 3

        /**
         * The length of the bit set array.
         */
        Set_array_length,  // 4

        /**
         * The maximum permitted length of the bit set array.
         */
        Set_array_max_length,  // 5

        /**
         * The number of level2 areas.
         */
        Level2_areas,  // 6

        /**
         * The length of the level2 areas.
         */
        Level2_area_length,  // 7

        /**
         * The total number of level3 blocks in use.
         */
        Level3_blocks,  // 8

        /**
         * The length of the level3 blocks.
         */
        Level3_block_length,  // 9

        /**
         * Is the value that determines how the *toString*() conversion is
         * performed.
         * @see .toStringCompaction
         */
        Compaction_count_value // 10
    }

    //=============================================================================
    //  A set of cached statistics values, recomputed when necessary
    //=============================================================================
    /**
     * This class holds the values related to various statistics kept about the
     * bit set. These values are not kept continuously up-to-date. Whenever the
     * values become invalid, the field *hash* is set to zero, indicating
     * that an update is required.
     *
     * @see .statisticsUpdate
     */
    protected inner class Cache {
        /**
         * *hash* is updated by the *statisticsUpdate*() method.
         * If the *hash* value is zero, it is assumed that ***all***
         * the cached values are stale, and must be updated.
         */
        @Transient
        var hash: Int = 0

        /**
         * *size* is updated by the *statisticsUpdate*() method.
         * If the *hash* value is zero, it is assumed the all the cached
         * values are stale, and must be updated.
         */
        @Transient
        var size: Int = 0

        /**
         * *cardinality* is updated by the *statisticsUpdate*() method.
         * If the *hash* value is zero, it is assumed the all the cached
         * values are stale, and must be updated.
         */
        @Transient
        var cardinality: Int = 0

        /**
         * *length* is updated by the *statisticsUpdate*() method.
         * If the *hash* value is zero, it is assumed the all the cached
         * values are stale, and must be updated.
         */
        @Transient
        var length: Int = 0

        /**
         * *count* is updated by the *statisticsUpdate*() method.
         * If the *hash* value is zero, it is assumed the all the cached
         * values are stale, and must be updated.
         */
        @Transient
        var count: Int = 0

        /**
         * *a2Count* is updated by the *statisticsUpdate*()
         * method, and will only be correct immediately after a full update. The
         * *hash* value is must be zero for all values to be updated.
         */
        @Transient
        var a2Count: Int = 0

        /**
         * *a3Count* is updated by the *statisticsUpdate*() method,
         * and will only be correct immediately after a full update. The
         * *hash* value is must be zero for all values to be updated.
         */
        @Transient
        var a3Count: Int = 0
    }

    //=============================================================================
    //  Abstract Strategy super-class for Strategies describing logical operations
    //=============================================================================
    /**
     * This strategy class is used by the setScanner to carry out the a variety
     * of operations on this set, and usually a second set. The
     * *setScanner*() method of the main `SparseBitSet` class
     * essentially finds matching level3 blocks, and then calls the strategy to
     * do the appropriate operation on each of the elements of the block.
     *
     *
     * The symbolic constants control optimisation paths in the
     * *setScanner*() method of the main `SparseBitSet` class.
     *
     * @see SparseBitSet.setScanner
     */
    abstract class AbstractStrategy {
        /**
         * Properties of this strategy.
         *
         * @return      the int containing the bits representing the properties of
         * this strategy
         * @since       1.6
         */
        abstract fun properties(): Int

        /**
         * Instances of this class are to be serially reusable. To start a
         * particular use, an instance is (re-)started by calling this method. It is
         * passed the reference to the other bit set (usually to allow a check on
         * whether it is null or not, so as to simplify the implementation of the
         * *block*() method.
         *
         * @param       b the "other" set, for whatever checking is needed.
         * @since       1.6
         * @return      true -> if the cache should be set to zero
         */
        abstract fun start(b: SparseBitSet): Boolean

        /**
         * Deal with a scan that include a partial word within a level3 block. All
         * that is required is that the result be stored (if needed) into the
         * given a set block at the correct position, and that the operation only
         * affect those bits selected by 1 bits in the mask.
         *
         * @param       base the base index of the block (to be used if needed)
         * @param       u3 the index of the word within block
         * @param       a3 the level3 block from the *a* set.
         * @param       b3 the (nominal) level3 block from the *b* set (not null).
         * @param       mask for the (partial) word
         * @return      true if the resulting word is zero
         * @since       1.6
         */
        abstract fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean

        /**
         * Deals with a part of a block that consists of whole words, starting with
         * the given first index, and ending with the word before the last index.
         * For the words processed, the return value should indicate whether all those
         * resulting words were zero, or not.
         *
         * @param       base the base index of the block (to be used if needed)
         * @param       u3 the index of the first word within block to process
         * @param       v3 the index of the last word, which may be within block
         * @param       a3 the level3 block from the *a* set.
         * @param       b3 the (nominal) level3 block from the *b* set (not null).
         * @return      true if the words scanned within the level3 block were all zero
         * @since       1.6
         */
        abstract fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean

        /**
         * This is called to finish the processing started by the strategy (if there
         * needs to be anything done at all).
         *
         * @param       a2Count possible count of level2 areas in use
         * @param       a3Count possible count of level3 blocks in use
         * @since       1.6
         */
        open fun finish(a2Count: Int, a3Count: Int) {
        }

        /**
         * Check whether a level3 block is all zero.
         *
         * @param       a3 the block from the *a* set
         * @return      true if the values of the level3 block are all zero
         *
         * @since       1.6
         */
        fun isZeroBlock(a3: LongArray?): Boolean {
            if (a3 != null) {
                for (word in a3) if (word != 0L) return false
            }
            return true
        }

        companion object {
            /** If the operation requires that when matching level2 areas or level3
             * blocks are null, that no action is required, then this property is
             * required. Corresponds to the top-left entry in the logic diagram for the
             * operation being 0. For all the defined actual logic operations ('and',
             * 'andNot', 'or', and 'xor', this will be true, because for all these,
             * "false" op "false" = "false".
             */
            const val F_OP_F_EQ_F: Int = 0x1

            /** If when level2 areas or level3 areas from the this set are null will
             * require that area or block to remain null, irrespective of the value of
             * the matching structure from the other set, then this property is required.
             * Corresponds to the first row in the logic diagram being all zeros. For
             * example, this is true for 'and' as well as 'andNot', and for 'clear', since
             * false" & "x" = "false", and "false" &! "x" = "false".
             */
            const val F_OP_X_EQ_F: Int = 0x2

            /** If when level2 areas or level3 areas from the other set are null will
             * require the matching area or block in this set to be set to null,
             * irrespective of the current values in the matching structure from the
             * this, then this property is required. Corresponds to the first column
             * in the logic diagram being all zero. For example, this is true for
             * 'and', since "x" & "false" = "false", as well as for 'clear'.
             */
            const val X_OP_F_EQ_F: Int = 0x4

            /** If when a level3 area from the other set is null will require the
             * matching area or block in this set to be left as it is, then this property
             * is required. Corresponds to the first column of the logic diagram being
             * equal to the left hand operand column. For example, this is true for 'or',
             * 'xor', and 'andNot', since for all of these "x" op "false" = "x".
             */
            const val X_OP_F_EQ_X: Int = 0x8
        }
    }

    //=============================================================================
    //  Strategies based on the Strategy super-class describing logical operations
    //=============================================================================
    /**
     * And of two sets. Where the *a* set is zero, it remains zero (i.e.,
     * without entries or with zero words). Similarly, where the *b* set is
     * zero, the *a* becomes zero (i.e., without entries).
     *
     *
     * If level1 of the *a* set is longer than level1 of the bit set
     * *b*, then the unmatched virtual "entries" of the *b* set (beyond
     * the actual length of *b*) corresponding to these are all false, hence
     * the result of the "and" operation will be to make all these entries in this
     * set to become false--hence just remove them, and then scan only those
     * entries that could match entries in the bit set*b*. This clearing of
     * the remainder of the *a* set is accomplished by selecting both
     * *F_OP_X_EQ_F* and *X_OP_F_EQ_F*.
     *
     * <pre>
     * and| 0 1
     * 0| 0 0
     * 1| 0 1 <pre>
    </pre></pre> */
    class AndStrategy : AbstractStrategy() {
        //  AndStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + F_OP_X_EQ_F + X_OP_F_EQ_F
        }

        //  AndStrategy
        override fun start(b: SparseBitSet): Boolean {
            if (b == null) throw NullPointerException()
            return true
        }

        //  AndStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return (b3[u3] or mask.inv().let { a3[u3] = a3[u3] and it; a3[u3] }) == 0L
        }

        //  AndStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) isZero =
                isZero and ((b3[w3].let { a3[w3] = a3[w3] and it; a3[w3] }) == 0L)
            return isZero
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * AndNot of two sets. Where the *a* set is zero, it remains zero
     * (i.e., without entries or with zero words). On the other hand, where the
     * *b* set is zero, the *a* remains unchanged.
     *
     *
     * If level1 of the *a* set is longer than level1 of the bit set
     * *b*, then the unmatched virtual "entries" of the *b* set (beyond
     * the actual length of *b*) corresponding to these are all false, hence
     * the result of the "and" operation will be to make all these entries in this
     * set to become false--hence just remove them, and then scan only those
     * entries that could match entries in the bit set*b*. This clearing of
     * the remainder of the *a* set is accomplished by selecting both
     * *F_OP_X_EQ_F* and *X_OP_F_EQ_F*.
     *
     * <pre>
     * andNot| 0 1
     * 0| 0 0
     * 1| 1 0 <pre>
    </pre></pre> */
    class AndNotStrategy : AbstractStrategy() {
        //  AndNotStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + F_OP_X_EQ_F + X_OP_F_EQ_X
        }

        //  AndNotStrategy
        override fun start(b: SparseBitSet): Boolean {
            if (b == null) throw NullPointerException()
            return true
        }

        //  AndNotStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return ((b3[u3] and mask).inv().let { a3[u3] = a3[u3] and it; a3[u3] }) == 0L
        }

        //  AndNotStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) isZero =
                isZero and ((b3[w3].inv().let { a3[w3] = a3[w3] and it; a3[w3] }) == 0L)
            return isZero
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Clear clears bits in the *a* set.
     *
     * <pre>
     * clear| 0 1
     * 0| 0 0
     * 1| 0 0 <pre>
    </pre></pre> */
    class ClearStrategy : AbstractStrategy() {
        //  ClearStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + F_OP_X_EQ_F
        }

        //  ClearStrategy
        override fun start(b: SparseBitSet): Boolean {
            return true
        }

        //  ClearStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return (mask.inv().let { a3[u3] = a3[u3] and it; a3[u3] }) == 0L
        }

        //  ClearStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            if (u3 != 0 || v3 != LENGTH3)  //  Optimisation
                for (w3 in u3 until v3) a3[w3] = 0L
            return true
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Copies the needed parts of the *b* set to the *a* set.
     *
     * <pre>
     * get| 0 1
     * 0| 0 1
     * 1| 0 1 <pre>
    </pre></pre> */
    class CopyStrategy : AbstractStrategy() {
        //  CopyStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + X_OP_F_EQ_F
        }

        //  CopyStrategy
        override fun start(b: SparseBitSet): Boolean {
            return true
        }

        //  CopyStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return ((b3[u3] and mask).also { a3[u3] = it }) == 0L
        }

        //  CopyStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true
            for (w3 in u3 until v3) isZero = isZero and ((b3[w3].also { a3[w3] = it }) == 0L)
            return isZero
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Equals compares bits in the *a* set with those in the *b* set.
     * None of the values in either set are changed, although the *a* set
     * may have all zero level 3 blocks replaced by null references (and
     * similarly at level 2).
     *
     * <pre>
     * equals| 0 1
     * 0| 0 -
     * 1| - - <pre>
    </pre></pre> */
    protected class EqualsStrategy : AbstractStrategy() {
        var result: Boolean = false // Used to hold result of the comparison

        //  EqualsStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F
        }

        //  EqualsStrategy
        override fun start(b: SparseBitSet): Boolean {
            if (b == null) throw NullPointerException()
            result = true
            return false
            /*  Equals does not change the content of the set, hence hash need
                not be reset. */
        }

        //  EqualsStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            val word = a3[u3]
            result = result and ((word and mask) == (b3[u3] and mask))
            return word == 0L
        }

        //  EqualsStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) {
                val word = a3[w3]
                result = result and (word == b3[w3])
                isZero = isZero and (word == 0L)
            }
            return isZero
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Flip inverts the bits of the *a* set within the given range.
     *
     * <pre>
     * flip| 0 1
     * 0| 1 1
     * 1| 0 0 <pre>
    </pre></pre> */
    class FlipStrategy : AbstractStrategy() {
        // FlipStrategy
        override fun properties(): Int {
            return 0
        }

        // FlipStrategy
        override fun start(b: SparseBitSet): Boolean {
            return true
        }

        // FlipStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return (mask.let { a3[u3] = a3[u3] xor it; a3[u3] }) == 0L
        }

        // FlipStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) isZero =
                isZero and ((0L.inv().let { a3[w3] = a3[w3] xor it; a3[w3] }) == 0L)
            return isZero
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Intersect has a true result if any word in the *a* set has a bit
     * in common with the *b* set. During the scan of the *a* set
     * blocks (and areas) that are all zero may be replaced with empty blocks
     * and areas (null references), but the value of the set is not changed
     * (which is why X_OP_F_EQ_F is not selected, since this would cause
     * parts of the *a* set to be zero-ed out).
     *
     * <pre>
     * intersect| 0 1
     * 0| 0 0
     * 1| 1 1 <pre>
    </pre></pre> */
    class IntersectsStrategy : AbstractStrategy() {
        /**
         * The boolean result of the intersects scan Strategy is kept here.
         */
        var result: Boolean = false

        //  IntersectsStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + F_OP_X_EQ_F
        }

        //  IntersectsStrategy
        override fun start(b: SparseBitSet): Boolean {
            if (b == null) throw NullPointerException()
            result = false
            return false
            /*  Intersect does not change the content of the set, hence hash
                need not be reset. */
        }

        //  IntersectsStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            val word = a3[u3]
            result = result or ((word and b3[u3] and mask) != 0L)
            return word == 0L
        }

        //  IntersectsStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) {
                val word = a3[w3]
                result = result or ((word and b3[w3]) != 0L)
                isZero = isZero and (word == 0L)
            }
            return isZero
        }
    }

    /**
     * Or of two sets. Where the *a* set is one, it remains one. Similarly,
     * where the *b* set is one, the *a* becomes one. If both sets have
     * zeros in corresponding places, a zero results. Whole blocks or areas that
     * are or become zero are replaced by null arrays.
     *
     *
     * If level1 of the *a* set is longer than level1 of the bit set
     * *b*, then the unmatched entries of the *a* set (beyond
     * the actual length of *b*) corresponding to these remain unchanged. *
     * <pre>
     * or| 0 1
     * 0| 0 1
     * 1| 1 1 <pre>
    </pre></pre> */
    class OrStrategy : AbstractStrategy() {
        //  OrStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + X_OP_F_EQ_X
        }

        //  OrStrategy
        override fun start(b: SparseBitSet): Boolean {
            if (b == null) throw NullPointerException()
            return true
        }

        //  OrStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return (b3[u3] and mask.let { a3[u3] = a3[u3] or it; a3[u3] }) == 0L
        }

        //  OrStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) isZero =
                isZero and ((b3[w3].let { a3[w3] = a3[w3] or it; a3[w3] }) == 0L)
            return isZero
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Set creates entries everywhere within the range. Hence no empty level2
     * areas or level3 blocks are ignored, and no empty (all zero) blocks are
     * returned.
     *
     * <pre>
     * set| 0 1
     * 0| 1 1
     * 1| 1 1 <pre>
    </pre></pre> */
    class SetStrategy : AbstractStrategy() {
        //  SetStrategy
        override fun properties(): Int {
            return 0
        }

        //  SetStrategy
        override fun start(b: SparseBitSet): Boolean {
            return true
        }

        //  SetStrategy
        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            a3[u3] = a3[u3] or mask
            return false
        }

        //  SetStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            for (w3 in u3 until v3) a3[w3] = 0L.inv()
            return false // set always sets bits
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * Update the seven statistics that are computed for each set. These are
     * updated by calling *statisticsUpdate*, which uses this strategy.
     *
     * <pre>
     * update| 0 1
     * 0| 0 0
     * 1| 1 1 <pre>
     *
     * @see SparseBitSet.statisticsUpdate
    </pre></pre> */
    protected inner class UpdateStrategy : AbstractStrategy() {
        /**
         * Working space for find the size and length of the bit set. Holds the
         * index of the first non-empty word in the set.
         */
        @Transient
        protected var wMin: Int = 0

        /**
         * Working space for find the size and length of the bit set. Holds copy of
         * the first non-empty word in the set.
         */
        @Transient
        protected var wordMin: Long = 0

        /**
         * Working space for find the size and length of the bit set. Holds the
         * index of the last non-empty word in the set.
         */
        @Transient
        protected var wMax: Int = 0

        /**
         * Working space for find the size and length of the bit set. Holds a copy
         * of the last non-empty word in the set.
         */
        @Transient
        protected var wordMax: Long = 0

        /**
         * Working space for find the hash value of the bit set. Holds the
         * current state of the computation of the hash value. This value is
         * ultimately transferred to the Cache object.
         *
         * @see SparseBitSet.Cache
         */
        @Transient
        protected var hash: Long = 0

        /**
         * Working space for keeping count of the number of non-zero words in the
         * bit set. Holds the current state of the computation of the count. This
         * value is ultimately transferred to the Cache object.
         *
         * @see SparseBitSet.Cache
         */
        @Transient
        protected var count: Int = 0

        /**
         * Working space for counting the number of non-zero bits in the bit set.
         * Holds the current state of the computation of the cardinality.This
         * value is ultimately transferred to the Cache object.
         *
         * @see SparseBitSet.Cache
         */
        @Transient
        protected var cardinality: Int = 0

        //  UpdateStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + F_OP_X_EQ_F
        }

        /**
         * This method initializes the computations by suitably resetting cache
         * fields or working fields.
         *
         * @param       b the other SparseBitSet, for checking if needed.
         *
         * @since       1.6
         */
        override fun start(b: SparseBitSet): Boolean {
            hash = 1234L // Magic number
            wMin = -1 // index of first non-zero word
            wordMin = 0L // word at that index
            wMax = 0 // index of last non-zero word
            wordMax = 0L // word at that index
            count = 0 // count of non-zero words in whole set
            cardinality = 0 // count of non-zero bits in the whole set
            return false
        }

        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            val word = a3[u3]
            val word1 = word and mask
            if (word1 != 0L) compute(base + u3, word1)
            return word == 0L
        }

        //  UpdateStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in 0 until v3) {
                val word = a3[w3]
                if (word != 0L) {
                    isZero = false
                    compute(base + w3, word)
                }
            }
            return isZero
        }

        //  UpdateStrategy
        override fun finish(a2Count: Int, a3Count: Int) {
            cache!!.a2Count = a2Count
            cache!!.a3Count = a3Count
            cache!!.count = count
            cache!!.cardinality = cardinality
            cache!!.length = (wMax + 1) * LENGTH4 - wordMax.countLeadingZeroBits()
            cache!!.size = (cache!!.length - wMin * LENGTH4 - wordMin.countTrailingZeroBits()) /*Long.numberOfTrailingZeros(wordMin))*/
            cache!!.hash = ((hash shr Int.SIZE_BITS) xor hash).toInt()
        }

        /**
         * This method does the accumulation of the statistics. It must be called
         * in sequential order of the words in the set for which the statistics
         * are being accumulated, and only for non-null values of the second
         * parameter.
         *
         * Two of the values (a2Count and a3Count) are not updated here,
         * but are done in the code near where this method is called.
         *
         * @param       index the word index of the word supplied
         * @param       word the long non-zero word from the set
         * @since       1.6
         */
        private fun compute(index: Int, word: Long) {
            /*  Count the number of actual words being used. */
            ++count
            /*  Continue to accumulate the hash value of the set. */
            hash = hash xor word * (index + 1).toLong()
            /*  The first non-zero word contains the first actual bit of the
                set. The location of this bit is used to compute the set size. */
            if (wMin < 0) {
                wMin = index
                wordMin = word
            }
            /*  The last non-zero word contains the last actual bit of the set.
                The location of this bit is used to compute the set length. */
            wMax = index
            wordMax = word
            /*  Count the actual bits, so as to get the cardinality of the set. */
            cardinality += word.countOneBits() //Long.bitCount(word)
        }
    }

    //-----------------------------------------------------------------------------
    /**
     * The XOR of level3 blocks is computed.
     *
     * <pre>
     * xor| 0 1
     * 0| 0 1
     * 1| 1 0 <pre>
    </pre></pre> */
    class XorStrategy : AbstractStrategy() {
        //  XorStrategy
        override fun properties(): Int {
            return F_OP_F_EQ_F + X_OP_F_EQ_X
        }

        //  XorStrategy
        override fun start(b: SparseBitSet): Boolean {
            if (b == null) throw NullPointerException()
            return true
        }

        override fun word(base: Int, u3: Int, a3: LongArray, b3: LongArray, mask: Long): Boolean {
            return (b3[u3] and mask.let { a3[u3] = a3[u3] xor it; a3[u3] }) == 0L
        }

        //  XorStrategy
        override fun block(base: Int, u3: Int, v3: Int, a3: LongArray, b3: LongArray): Boolean {
            var isZero = true //  Presumption
            for (w3 in u3 until v3) isZero =
                isZero and ((b3[w3].let { a3[w3] = a3[w3] xor it; a3[w3] }) == 0L)
            return isZero
        }
    }

    /**
     * Word and block **equals** strategy.
     */
    @Transient
    protected var equalsStrategy: EqualsStrategy? = null

    /**
     * Word and block **update** strategy.
     */
    @Transient
    protected lateinit var updateStrategy: UpdateStrategy


    companion object {
        /**
         * The compaction count default.
         */
        var compactionCountDefault: Int = 2 // Note: this is not final!

        //==============================================================================
        //  The critical parameters. These are set up so that the compiler may
        //  pre-compute all the values as compile-time constants.
        //==============================================================================
        /**
         * The number of bits in a long value.
         */
        protected val LENGTH4: Int = Long.SIZE_BITS

        /**
         * The number of bits in a positive integer, and the size of permitted index
         * of a bit in the bit set.
         */
        protected val INDEX_SIZE: Int = Int.SIZE_BITS - 1

        /**
         * The label (index) of a bit in the bit set is essentially broken into
         * 4 "levels". Respectively (from the least significant end), level4, the
         * address within word, the address within a level3 block, the address within
         * a level2 area, and the level1 address of that area within the set.
         *
         * LEVEL4 is the number of bits of the level4 address (number of bits need
         * to address the bits in a long)
         */
        protected const val LEVEL4: Int = 6

        /**
         * LEVEL3 is the number of bits of the level3 address.
         */
        protected const val LEVEL3: Int = 5 // Do not change!

        /**
         * LEVEL2 is the number of bits of the level2 address.
         */
        protected const val LEVEL2: Int = 5 // Do not change!

        /**
         * LEVEL1 is the number of bits of the level1 address.
         */
        protected val LEVEL1: Int = INDEX_SIZE - LEVEL2 - LEVEL3 - LEVEL4

        /**
         * MAX_LENGTH1 is the maximum number of entries in the level1 set array.
         */
        protected val MAX_LENGTH1: Int = 1 shl LEVEL1

        /**
         * LENGTH2 is the number of entries in the any level2 area.
         */
        protected const val LENGTH2: Int = 1 shl LEVEL2

        /**
         * LENGTH3 is the number of entries in the any level3 block.
         */
        protected const val LENGTH3: Int = 1 shl LEVEL3

        /**
         * The shift to create the word index. (I.e., move it to the right end)
         */
        protected const val SHIFT3: Int = LEVEL4

        /**
         * MASK3 is the mask to extract the LEVEL3 address from a word index
         * (after shifting by SHIFT3).
         */
        protected const val MASK3: Int = LENGTH3 - 1

        /**
         * SHIFT2 is the shift to bring the level2 address (from the word index) to
         * the right end (i.e., after shifting by SHIFT3).
         */
        protected const val SHIFT2: Int = LEVEL3

        /**
         * UNIT is the greatest number of bits that can be held in one level1 entry.
         * That is, bits per word by words per level3 block by blocks per level2 area.
         */
        protected val UNIT: Int = LENGTH2 * LENGTH3 * LENGTH4

        /**
         * MASK2 is the mask to extract the LEVEL2 address from a word index
         * (after shifting by SHIFT3 and SHIFT2).
         */
        protected const val MASK2: Int = LENGTH2 - 1

        /**
         * SHIFT1 is the shift to bring the level1 address (from the word index) to
         * the right end (i.e., after shifting by SHIFT3).
         */
        protected const val SHIFT1: Int = LEVEL2 + LEVEL3

        /**
         * LENGTH2_SIZE is maximum index of a LEVEL2 page.
         */
        protected const val LENGTH2_SIZE: Int = LENGTH2 - 1

        /**
         * LENGTH3_SIZE is maximum index of a LEVEL3 page.
         */
        protected const val LENGTH3_SIZE: Int = LENGTH3 - 1

        /**
         * LENGTH4_SIZE is maximum index of a bit in a LEVEL4 word.
         */
        protected val LENGTH4_SIZE: Int = LENGTH4 - 1

        /** An empty level 3 block is kept for use when scanning. When a source block
         * is needed, and there is not already one in the corresponding bit set, the
         * ZERO_BLOCK is used (as a read-only block). It is a source of zero values
         * so that code does not have to test for a null level3 block. This is a
         * static block shared everywhere.
         */
        val ZERO_BLOCK: LongArray = LongArray(LENGTH3)

        /**
         * Performs a logical **AND** of the two given `SparseBitSet`s.
         * The returned `SparseBitSet` is created so that each bit in it
         * has the value `true` if and only if both the given sets
         * initially had the corresponding bits `true`, otherwise
         * `false`.
         *
         * @param       a a SparseBitSet
         * @param       b another SparseBitSet
         * @return      a new SparseBitSet representing the **AND** of the two sets
         * @since       1.6
         */
        fun and(a: SparseBitSet, b: SparseBitSet): SparseBitSet {
            val result = a.clone()
            result.and(b)
            return result
        }

        /**
         * Creates a bit set from thie first `SparseBitSet` whose
         * corresponding bits are cleared by the set bits of the second
         * `SparseBitSet`. The resulting bit set is created so that a bit
         * in it has the value `true` if and only if the corresponding bit
         * in the `SparseBitSet` of the first is set, and that same
         * corresponding bit is not set in the `SparseBitSet` of the second
         * argument.
         *
         * @param a     a SparseBitSet
         * @param b     another SparseBitSet
         * @return      a new SparseBitSet representing the **AndNOT** of the
         * two sets
         * @since       1.6
         */
        fun andNot(a: SparseBitSet, b: SparseBitSet): SparseBitSet {
            val result = a.clone()
            result.andNot(b)
            return result
        }

        /**
         * Performs a logical **OR** of the two given `SparseBitSet`s.
         * The returned `SparseBitSet` is created so that a bit in it has
         * the value `true` if and only if it either had the value
         * `true` in the set given by the first arguemetn or had the value
         * `true` in the second argument, otherwise `false`.
         *
         * @param       a a SparseBitSet
         * @param       b another SparseBitSet
         * @return      new SparseBitSet representing the **OR** of the two sets
         * @since       1.6
         */
        fun or(a: SparseBitSet, b: SparseBitSet): SparseBitSet {
            val result = a.clone()
            result.or(b)
            return result
        }

        /**
         * Performs a logical **XOR** of the two given `SparseBitSet`s.
         * The resulting bit set is created so that a bit in it has the value
         * `true` if and only if one of the following statements holds:
         *
         *  * A bit in the first argument has the value `true`, and the
         * corresponding bit in the second argument has the value
         * `false`.
         *  * A bit in the first argument has the value `false`, and the
         * corresponding bit in the second argument has the value
         * `true`.
         *
         * @param       a a SparseBitSet
         * @param       b another SparseBitSet
         * @return      a new SparseBitSet representing the **XOR** of the two sets
         * @since       1.6
         */
        fun xor(a: SparseBitSet, b: SparseBitSet): SparseBitSet {
            val result = a.clone()
            result.xor(b)
            return result
        }

        //==============================================================================
        //      Internal methods
        //==============================================================================
        /**
         * Throw the exception to indicate a range error. The `String`
         * constructed reports all the possible errors in one message.
         *
         * @param       i lower bound for a operation
         * @param       j upper bound for a operation
         * @exception   IndexOutOfBoundsException indicating the range is not valid
         * @since       1.6
         */
        @Throws(IndexOutOfBoundsException::class)
        protected fun throwIndexOutOfBoundsException(i: Int, j: Int) {
            var s = ""
            if (i < 0) s += "(i=$i) < 0"
            if (i == Int.MAX_VALUE) s += "(i=$i)"
            if (j < 0) s += (if (s.isEmpty()) "" else ", ") + "(j=" + j + ") < 0"
            if (i > j) s += (if (s.isEmpty()) "" else ", ") + "(i=" + i + ") > (j=" + j + ")"
            throw IndexOutOfBoundsException(s)
        }

        /**
         * serialVersionUID
         */
        private const val serialVersionUID = -6663013367427929992L

        //-----------------------------------------------------------------------------
        /**
         * Word and block **and** strategy.
         */
        @Transient
        protected val andStrategy: AndStrategy = AndStrategy()

        /**
         * Word and block **andNot** strategy.
         */
        @Transient
        protected val andNotStrategy: AndNotStrategy = AndNotStrategy()

        /**
         * Word and block **clear** strategy.
         */
        @Transient
        protected val clearStrategy: ClearStrategy = ClearStrategy()

        /**
         * Word and block **copy** strategy.
         */
        @Transient
        protected val copyStrategy: CopyStrategy = CopyStrategy()

        /**
         * Word and block **flip** strategy.
         */
        @Transient
        protected val flipStrategy: FlipStrategy = FlipStrategy()

        /**
         * Word and block **intersects** strategy.
         */
        @Transient
        protected var intersectsStrategy: IntersectsStrategy = IntersectsStrategy()

        /**
         * Word and block **or** strategy.
         */
        @Transient
        protected val orStrategy: OrStrategy = OrStrategy()

        /**
         * Word and block **set** strategy.
         */
        @Transient
        protected val setStrategy: SetStrategy = SetStrategy()

        /**
         * Word and block **xor** strategy.
         */
        @Transient
        protected val xorStrategy: XorStrategy = XorStrategy()
    }
}